package com.leetcode.no40;

import java.util.*;

// 第 39 题：candidates 中的数字可以无限制重复被选取；
//第 40 题：candidates 中的每个数字在每个组合中只能使用一次。

public class Solution {

    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates.length < 1) {
            return res;
        }

        // 记录「路径」
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(candidates, track, 0, target);

        return res;
    }

    public void backtrack(int[] candidates, LinkedList<Integer> track, int index, int target) {
        if (target == 0) {
            res.add(track);
            return;
        }

        for (int i = 0; i < candidates.length; i++ ){
            // 剪去不合法的分支
            if (candidates[i] > target && candidates[i]==candidates[i-1]) {
                continue;
            }

            // 做选择
            track.add(candidates[i]);
            // 进入下一层决策树
            backtrack(
                    candidates,
                    track,
                    i,
                    target - candidates[i]
            );

            // 取消选择
            track.removeLast();
        }
    }

}
